package leetcode_900;

/**
 *@author 周杨
 *LargestSumOfAverages_813_ 给定一个正整数数组和一个正整数 n 问数组分成n个连续子数组 最大平均值和是多少
 *describe:用动态规划和数组和 dp[num][index]->dp[num-1][pre]+(sum[index]-sum[pre])/index-pre AC 29%
 *2018年10月27日 下午3:22:00
 */
public class LargestSumOfAverages_813_ {
	public static void main(String[] args) {
		LargestSumOfAverages_813_ test=new LargestSumOfAverages_813_();
		System.out.println(
				test.largestSumOfAverages(new int[] {1,2,3,4,5,6,7}, 4));
	}
	
	public double largestSumOfAverages(int[] A, int K) {
        for(int i=1;i<A.length;++i) {
        	A[i]+=A[i-1];//构造区间和
        }
        double dp[][]=new double[K][A.length];
        for(int i=0;i<K;++i) {//先看分成几段  后面的状态构造前面的状态
        	for(int j=0;j<A.length;++j) {
        		if(i==0) {//仅能构造一段
        			dp[i][j]=A[j]/(double)(j+1);
        		}
        		else {
        			dp[i][j]=dp[i-1][j];
        			for(int k=0;k<j;++k) {
        				dp[i][j]=Math.max(dp[i][j], dp[i-1][k]+(A[j]-A[k])/(double)(j-k));
        			}
        		}
        	}
        }
        return dp[K-1][A.length-1];
    }
}
